走迷宫
题目 走迷宫
思路分析
逻辑与dfs差不多 都是可以先默写上 dx，dy 以及isVaild
拓展也是4个方向 不过得先存在队列里面 先进先出的方式处理
另外不同的是 用一个d数组代替st数组 现在要记录每个点距离起点的距离 也可以等效地用来判断某个点用没用过 并多维护了一些信息
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef pair<int,int> PII;
const int N=110;
int g[N][N],d[N][N];
int n,m;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool isVaild(int x,int y){
return x>=1 && x<=n && y>=1 && y<=m && d[x][y]==-1;
}
int bfs(int x,int y){
queue<PII> q;
memset(d,-1,sizeof d);
d[x][y]=0;
q.push({x,y});
while(!q.empty()){
auto cur=q.front();
int ux=cur.first,uy=cur.second;
q.pop();
for(int i=0;i<4;i++){
int nx=ux+dx[i],ny=uy+dy[i];
if(isVaild(nx,ny) && g[nx][ny]==0){
d[nx][ny]=d[ux][uy]+1;
q.push({nx,ny});
}
}
}
return d[n][m];
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
}
}
cout<<bfs(1,1);
return 0;
}
💬 评论